/**
 \* Created with IntelliJ IDEA.
 \* User: Administrator
 \* Date: 2022/9/5
 \* Time: 10:31
 \* To change this template use File | Settings | File Templates.
 \* Description:
 \*/
public class test1 {
    public static void main(String[] args) {
        int[] nums = new int[] { 1, 3, 7, 8, 2, 9, 6, 0, 5, 4 };
//        sort3(nums, 0, nums.length - 1);
        sort4(nums);
        for (int num : nums)
            System.out.print(num + " ");
    }

    public static void sort5(int[]nums, int start, int end){
        if(start < end){
            int mid = (start + end) /2;
            sort5(nums,start,mid);
            sort5(nums,mid+1,end);
            merge(nums,start,end);
        }
    }
    public static void merge(int[] nums,int left,int right){
        int[] temp = new int[nums.length];
        int mid = left + (right - left) / 2;
        int p1 = left;
        int p2 = mid + 1;
        int k = left;
        while (p1 <= mid && p2 <= right){
            if(nums[p1] <= nums[p2]){
                temp[k++] = nums[p1++];
            }else{
                temp[k++] = nums[p2++];
            }
        }
        while(p1 <= mid){
            temp[k++] = nums[p1++];
        }
        while (p2 <= right){
            temp[k++] = nums[p2++];
        }
        for(int i = left; i <= right;i++){
            nums[i] = temp[i];
        }
    }

    public static void sort4(int[] nums){
        int n = nums.length;
        for(int i = 0 ; i < n - 1;i++){
            int min = i;
            for(int j = i + 1; j < n;j++){
                if(nums[j] < nums[min]){
                    min  = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        }
    }

    public static void sort3(int[] nums,int start,int end){
        if(start > end){
            return;
        }
        int left = start;
        int right = end;
        int temp = nums[left];
        while(left < right){
            while (left < right && nums[right] >= temp){
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= temp){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = temp;
        sort3(nums,start,left - 1);
        sort3(nums,left + 1,end);
    }

    public static void sort1(int[] nums){
        int n = nums.length;
        int pos,cur;
        for(int i = 1; i < n; i++){
               pos = i - 1;
            cur = nums[i];
            while (pos >= 0 && cur < nums[pos]){
                nums[pos + 1] = nums[pos];
                pos--;
            }
            nums[pos + 1] = cur;
        }
    }
    public static void sort(int[] nums){
        for(int i = 0; i < nums.length;i++){
            for(int j = 0 ; j < nums.length-1;j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }
}
